package com.learn.algorithm.unionfind;

public class CouplesHoldingHands {
    public static final int MAX = 32;
    public static final int[] father = new int[MAX];
    public static final int[] size = new int[MAX];
    public static int sets = 0;

    public int minSwapsCouples(int[] row) {
        int n = row.length;
        build(n / 2);
        for (int i = 0; i < n; i += 2) {
            union(row[i] / 2, row[i + 1] / 2);
        }
        return n / 2 - sets;
    }

    public static void build(int n) {
        for (int i = 0; i < n; i++) {
            father[i] = i;
            size[i] = 1;
        }
        sets = n;
    }

    public static int find(int x) {
        while (x != father[x]) {
            x = father[x];
        }
        return x;
    }

    public static void union(int a, int b) {
        int fx = find(a);
        int fy = find(b);
        if (fx == fy) {
            return;
        }
        father[fx] = fy;
        sets--;
    }
}
